<?php
/**
 * @title 2542. 最大子序列的分数
 * @author start2004
 */

// ini_set("memory_limit", "128M");

// class Solution {
//
//     function find() {
//
//     }
// }


class Solution {

    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @param Integer $k
     * @return Integer
     */
    function maxScore($nums1, $nums2, $k) {
        /**
         * @since 2024-01-05 nums2从小到大排序
         */
        array_multisort($nums2, SORT_ASC, SORT_NUMERIC, $nums1);
        // return [$nums1, $nums2];

        /**
         * @since 2024-01-05 数组元素总数
         */
        $count = count($nums1);

        /**
         * @since 2024-01-05 最小堆，求nums1的第k大数，前k个数总和
         * @since 2024-01-05 哈希数组，放nums1剩下的元素
         */
        $minHeap = new SplMinHeap();
        $hashArray = [];
        $sum = 0;

        /**
         * @since 2024-01-05 先进k个数
         */
        for ($i=0; $i<$k; $i++) {
            $minHeap->insert($nums1[$i]);
            $sum += $nums1[$i];
        }

        /**
         * @since 2024-01-05 遍历nums1剩下的元素
         */
        for (; $i<$count; $i++) {
            /**
             * @since 2024-01-05 如果当前元素比堆顶元素大，替换堆顶元素
             */
            if ($nums1[$i] > $minHeap->top()) {
                /**
                 * @since 2024-01-05 当前最小堆顶元素top出堆，更新sum
                 */
                $top = $minHeap->extract();
                $sum -= $top;
                $sum += $nums1[$i];

                /**
                 * @since 2024-01-05 更大数nums1[i]入最小堆
                 * @since 2024-01-05 原栈顶元素top，入哈希
                 */
                $minHeap->insert($nums1[$i]);
            } else {
                $top = $nums1[$i];
            }

            /**
             * @since 2024-01-06 更小的元素进哈希数组
             */
            if(isset($hashArray[$top])){
                $hashArray[$top]++;
            } else {
                $hashArray[$top] = 1;
            }
        }

        /**
         * @since 2024-01-06 哈希数组键值排序，哈希指针
         */
        $keyArray = array_keys($hashArray);
        sort($keyArray);
        $keyPoint = count($keyArray)-1;

        /**
         * @since 2024-01-05 最大乘积
         */
        $maxNum = 0;

        /**
         * @since 2024-01-05 遍历nums2，保证有$k-1元素在后面
         */
        for($i=0; $i<=($count-$k); $i++){
            /**
             * @since 2024-01-05 nums2[i]对应的nums1[i]元素，如果在前K个元素中
             */
            $top = $minHeap->top();
            // echo "nums1[{$i}] = {$nums1[$i]}, nums2[{$i}] = {$nums2[$i]}, top={$top}\n";

            /**
             * @since 2024-01-06 判断是否在堆中
             */
            if($nums1[$i] >= $top){
                $maxNum = max($maxNum, $nums2[$i] * $sum);
                // echo "sum={$sum}\n";

                /**
                 * @since 2024-01-06 nums1[i]已经使用，需要从剩下的元素中选个最大值入堆
                 */
                while($keyPoint>=0 AND $hashArray[$keyArray[$keyPoint]] == 0){
                    $keyPoint--;
                }
                if($keyPoint>=0){
                    /**
                     * @since 2024-01-06 剩下的最大值，入堆
                     */
                    $keyMax = $keyArray[$keyPoint];
                    $minHeap->insert($keyMax);

                    /**
                     * @since 2024-01-06 更新sum
                     */
                    $sum = $sum - $nums1[$i] + $keyMax;
                    // echo "update sum={$sum}, keyMax={$keyMax}\n";

                    /**
                     * @since 2024-01-06 哈希数量-1
                     */
                    $hashArray[$keyMax]--;
                }
            } elseif($nums1[$i] < $top){
                /**
                 * @since 2024-01-05 不在前K个元素中，去掉第K大元素，加上nums1[i]
                 */
                $maxNum = max($maxNum, $nums2[$i] * ($sum - $top + $nums1[$i]));
                // echo "sum=", ($sum - $top + $nums1[$i]), PHP_EOL;

                /**
                 * @since 2024-01-06 nums1[i]已经使用，哈希数量-1
                 */
                $hashArray[$nums1[$i]]--;
            } else {}
        }

        /**
         * @return Integer
         */
        return $maxNum;
    }
}

/**
 * @url http://127.0.0.1/leetcode/202401/2024.01.05_6.php
 */
$datas = [
    [[1,3,3,2], [2,1,3,4], 3], // 12
    [[4,2,3,1,1], [7,5,10,9,6], 1], // 30
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    if(count($data) <= 20){
        var_dump($data);
    } else {
        var_dump(count($data));
    }

    $obj = new Solution();
    $result = $obj->maxScore(...$data);
    // $result = $obj->($xhprof->tree($data));
    // $result = $obj->($xhprof->listNode($data));
    // $result = $obj->find(...$data);
    var_dump($result);
    // if(count($result)<=20){
    //     var_dump($result);
    // } else {
    //     var_dump(count($result));
    // }
    echo str_repeat(PHP_EOL, 3);
    echo str_repeat("<br>", 3);
}

// foreach ($datas as $data){
//     $obj = new $data[0][0](...$data[1][0]);
//
//     for ($i=1; $i<count($data[0]); $i++){
//         $func = $data[0][$i];
//         $param = $data[1][$i];
//         $result = $obj->$func(...$param);
//
//         echo $data[0][$i] ."(\"". implode(",", $data[1][$i]) ."\") ";
//             if($result === true){
//                 echo "True";
//             } elseif($result === false) {
//                 echo "False";
//             } elseif($result === null) {
//                 echo "Null";
//             } elseif(is_array($result)) {
//                 var_dump($result);
//             } else {
//                 echo $result;
//             }
//         echo PHP_EOL;
//     }
//
//     echo str_repeat(PHP_EOL, 3);
// }
$xhprof->end();
